package com.hdu.hot100.trick;

public class lc31 {


    class Solution {
        public void nextPermutation(int[] nums)
        {
            // 7 6 4 5 3 2 1
            int index = -1;
            for (int i = nums.length - 1; i > 0; i--)
            {
                if (nums[i] > nums[i - 1])
                {
                    index = i - 1;
                    break;
                }
            }

            //          index
            //           ↓
            // 7    6    4    5    3    2    1
            if (index == - 1)
            {
                swap(nums, 0, nums.length - 1);
                return;
            }

            int index2 = -1;
            for (int i = nums.length - 1; i > index; i--)
            {
                if (nums[i] > nums[index])
                {
                    index2 = i;
                    break;
                }
            }

            //          index index2
            //           ↓
            // 7    6    4    5    3    2    1

            int tmp = nums[index];
            nums[index] = nums[index2];
            nums[index2] = tmp;

            //          index index2
            //           ↓    ↓
            // 7    6    5    4    3    2    1
            swap(nums, index + 1, nums.length - 1);
        }

        void swap(int[] nums, int l, int r)
        {
            while (l < r)
            {
                int tmp = nums[l];
                nums[l] = nums[r];
                nums[r] = tmp;
                l++;
                r--;
            }
        }
    }

}
